package src.dynamic_programming;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author starsea
 * @date 2024-09-17 15:36
 */

public class Test15 {
    public static void main(String[] args) {
        //String str="leetcode";
        //List<String> words=new ArrayList<>();
        //words.add("leet");
        //words.add("code");
        //boolean c=wordBreak(str,words);
        //System.out.println(c);
        //int[] arr={0,2,3,4,0};
        //int [] t=twoSum(arr,0);
        //String version1 = "1.01";
        //String version2 = "1.001";
        //int c=compareVersion(version1,version2);
        //int[] arr={1,2,5};
        //int c=coinChange(arr,11);
        String str="10200";
        String s=removeKdigits(str,1);

    }
    public static String removeKdigits(String num, int k) {
        Stack<Integer> stack=new Stack<>();
        StringBuffer buffer=new StringBuffer();
        int i=0;
        for(;i<num.length() && k>0;)
        {
            int c=num.charAt(i)-'0';
            if(stack.isEmpty() || (stack.peek()<c &&  stack.peek()!=0) ) {
                stack.push(c);
                buffer.append(c);
                i++;
            }else
            {
                stack.pop();
                buffer.deleteCharAt(buffer.length()-1);
                k--;
            }
        }
        buffer.append(num.substring(i,num.length()));
        return buffer.toString();

    }
    public static int coinChange(int[] coins, int amount) {
        int n=coins.length;
        int[][] dp=new int[n+1][amount+1];
        for(int j=1;j<=amount;j++)
        {
            dp[0][j]=0x3f3f3f;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=amount;j++)
            {
                dp[i][j]=dp[i-1][j];
                if(j>=coins[i-1])
                {
                    dp[i][j]=Math.min(dp[i][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }
        return dp[n][amount]>=0x3f3f3f? -1:dp[n][amount];
    }

    public static int compareVersion(String version1, String version2) {
        String[] one=version1.split("\\.");
        String[] two=version2.split("\\.");
        for(int i=0;i<one.length;i++)
        {
            int a=Integer.parseInt(one[i]);
            int b=Integer.parseInt(two[i]);
            if(a>b)
            {
                return 1;
            }else if(b>a)
            {
                return -1;
            }
        }
        return 0;
    }
    public static int[] twoSum(int[] nums, int target) {

        int[] arr=new int[2];
        for(int i=0;i<nums.length-1;i++)
        {
            int tar=target-nums[i];
            int tmp=maxPost(nums,i+1,tar);
            if(tmp!=-1)
            {
                arr[0]=i;
                arr[1]=tmp;
                return arr;
            }

        }
        return arr;
    }
    public static int maxPost(int[] nums,int s,int tar)
    {
        int right=nums.length;
        while(s<=right)
        {
            int mid=s+(right-s)/2;
            if(nums[mid]> tar)
            {
                right=mid;
            }else if(nums[mid]<tar)
            {
                s=mid+1;
            }else
            {
                return mid;
            }
        }
        return -1;
    }
    public static boolean wordBreak(String s, List<String> wordDict) {
        int n=s.length();
        boolean[] dp=new boolean[n+1];
        s=" "+s;
        dp[0]=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j>0;j--)
            {
                String tmp=s.substring(j,i+1);
                if(dp[j-1]==true && wordDict.contains(tmp))
                {
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];


    }
}
